#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+9;
const int INF=1e18;
int n,C;
int a[maxn];
int dp[maxn];
int f[maxn];
int tmp[maxn];
signed main()
{
	freopen("minimize.in","r",stdin);
    freopen("minimize.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>C;
	int maxa=C;
	bool fl=1;
	for(int i=1;i<=n;i++) cin>>a[i],maxa=max(maxa,a[i]);
	for(int i=1;i<=n;i++) tmp[i]=a[i];
	for(int i=2;i<=n;i++) fl&=(a[i]>a[i-1]);
	sort(tmp+1,tmp+n+1);
	if(C==0) 
	{
		cout<<0<<'\n';
		return 0;
	}
	if(fl)
	{
		int sum=0;
		int res=INF;
		a[0]=a[1];
		for(int i=1;i<=n;i++) 
		{
			sum=sum+((a[i]-a[i-1])*(i-1));
			res=min(res,C*(n-i)+sum);
		}
		cout<<res<<'\n';
		return 0;
	}
	if(maxa<n)
	{
		for(int i=0;i<=maxa;i++) dp[i]=(i>=a[1])?(i-a[1]):C;
		for(int i=2;i<=n;i++)
		{
		    f[maxa+1]=INF;
		    for(int j=maxa;j>=0;j--) f[j]=min(f[j+1],dp[j]);
			for(int j=maxa;j>=0;j--)
			{
				dp[j]=f[j]+((j>=a[i])?(j-a[i]):C);
			}
		}
		int ans=INF;
		for(int i=0;i<=maxa;i++) ans=min(ans,dp[i]);
		cout<<ans<<'\n';
	}
	else 
	{
		for(int i=1;i<=n;i++) dp[i]=(tmp[i]>=a[1])?(tmp[i]-a[1]):C;
		//for(int i=n;i>=1;i--) cout<<tmp[i]<<" "<<dp[i]<<'\n';
		for(int i=2;i<=n;i++)
		{
			f[n+1]=INF;
			for(int j=n;j>=1;j--) f[j]=min(f[j+1],dp[j]);
			//cout<<'\n';
			for(int j=n;j>=1;j--) 
			{
				dp[j]=f[j]+((tmp[j]>=a[i])?(tmp[j]-a[i]):C);
			}
			//for(int j=n;j>=1;j--) cout<<dp[j]<<" ";cout<<'\n'<<'\n';
		}
		int ans=INF;
		for(int i=1;i<=n;i++) ans=min(ans,dp[i]);
		cout<<ans<<'\n';
	}
	return 0;
}
